#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int lcm1(int a,int b)
 {
 int n;
 for(n=1;;n++)
 {
	if(n%a == 0 && n%b == 0)
		return n;
 }
 }
 
int lcm2(int c,int d)
 {
	return (c*d)/gcd(c,d);
}

int gcd(int m, int n)
{
 int remainder;

	while (n != 0)
	{
		remainder = m % n; // m mod n
		if (remainder == 0)
			return n;
		m = n;
		n = remainder;
	}
}

int main(int argc, char *argv[])
{
  int a;
  int b;
  int c;
  int d;	
  double START,END;
 	
  printf("====== LCM (Least Common Multiple) 最小公倍數========\n ");
  printf("Please enter the first integer: ");
  scanf("%d", &a);
  printf("Please enter the second integer: ");
  scanf("%d", &b);
 
  START = clock();  	//記錄程式開始時間 

  c=lcm1(a,b);
 
  END = clock();		// 記錄程式結束時間 
	
  printf("進行運算所花費的時間： %f Second\n", ((END - START) / CLOCKS_PER_SEC));

  
  START = clock();  	//記錄程式開始時間 
  
  d=lcm2(a,b);
 
  END = clock();		// 記錄程式結束時間 
	
  printf("進行運算所花費的時間： %f Second\n", ((END - START) / CLOCKS_PER_SEC));
 
  printf("LCM 1 is %d\n",c);
  printf("LCM 2 is %d\n",d);
	
  system("PAUSE"); 
  return 0;
}